[doc] Les piles : type abstrait

Lien Moodle : https://moodle.epita.fr/mod/page/view.php?id=108758

Contenu du cours

Les piles : le type abstrait

3 opérations :

• sommet : pour connaître la valeur du sommet ;
• empiler : pour ajouter un nouvel élément ;
• dépiler : pour supprimer le sommet.

Les opérations sommet et dépiler sont des opérations partielles, puisqu'elles ne peuvent pas être appliquées à une pile vide.

Comme toujours, il est nécessaire d’avoir une opération d’ « initialisation » : pilevide et une pour vérifier si la structure contient des éléments : estvide.

Le type abstrait d’une pile est donc le suivant :

    types

        pile

    utilise

        booléen, élément

    opérations

        pilevide : → pile
         empiler : pile x élément → pile
         dépiler : pile → pile
          sommet : pile → élément
         estvide : pile → booléen

    préconditions

        dépiler(p) est-défini-ssi estvide(p) = Faux
         sommet(p) est-défini-ssi estvide(p) = Faux

    axiomes

        dépiler (empiler (p,e)) = p
        sommet (empiler (p,e)) = e
        estvide (pilevide) = Vrai
        estvide (empiler (p,e)) = Faux

    avec

        pile p
        élément e